Modern society has become heavily dependent on wireless networks in order to deliver information to diverse clients. People expect to be able to access dynamic data, such as stock quotes and traffic conditions, at any time, whether they are at home, in an office, or traveling. Wireless data distribution systems also have a broad range of applications in military networks, such as transmitting up-to-date battle information to tactical commanders in the field. New applications place high demands on the quality, availability, and timeliness of data distribution.
Distribution of dynamic information is a complex task and poses several major challenges. First, the underlying systems must be scalable, i.e., be able to serve a large number of clients in an efficient way. Second, the systems need to deal with heterogeneous clients that have different objectives, computational capabilities and access patterns. Next, each client must be able to receive the up-to-date information upon request with small delay and small expense of battery power. Finally, the data distribution systems must rely on the wireless infrastructure which is inherently asymmetric. In a typical wireless system, the downlink channel has higher bandwidth and capacity than the uplink channel. In addition, the downlink channel is operated by a powerful antenna, while the uplink channel is driven by a mobile device with limited power resources.
The intrinsic asymmetry of wireless infrastructure impacts the way information is delivered to clients. Recently, wireless data broadcast (see references [10,7,1]) has emerged as an attractive way to disseminate data to a large number of clients. In data broadcast systems, the server proactively transmits the information on the downlink channel and clients access data by listening to the channel. This approach enables the system to serve a large number of heterogeneous clients, minimizing power consumption and keeping the clients' locations secret.
FIG. 1 depicts a typical data broadcast system. The system includes the following components: the database, the server (scheduler), the broadcast channel, and the wireless clients. The server periodically accesses the database, retrieves the most recent data, encapsulates it into packets and sends the packets (or encoding thereof) over the broadcast channel. Upon a request for new information, the wireless clients listen to the channel and wait for the next transmitted packet.
The transmission schedule is a key element of wireless data broadcast systems. The transmission schedule is a time sequence that specifies the “best” data to transmit over the channel at any point in time. The goal in the design of transmission schedules is to minimize both the waiting time of the client and the staleness of the information. Waiting time is the amount of time spent by a client waiting for data, while the staleness captures the amount of time that passes from the moment the information is generated until it is delivered to the client. Low waiting time and staleness are necessary for providing Quality-of-Service guarantees to the end user. In addition, the waiting time is closely related to the amount of power spent by the client in order to obtain the information.
For example, consider the schedule depicted on FIG. 2. In this schedule, the server periodically transmits packets one after another, without encoding. In order to satisfy the request, a client has to listen to at least one packet from the beginning to the end. Indeed, since each packet describes the state of the information source at different points at time, the content of each packet is different. Therefore, even though the client may listen to (part of) previous packet (number i), it still needs to wait until the completion of packet i+1 in order to get the necessary update. This implies that the worst case waiting time of this schedule is equal to the length of the longest packet in the schedule. It can be shown that any deterministic schedule has a poor worst-case performance.
The design of optimum schedules for data broadcast has attracted a large body of research (see e.g., references [3,2,9,11,8,4,6] and references therein). The prior works in this area assume that clients' requests are distributed uniformly over time and focus on minimizing the average waiting time. However, in many settings of practical interest, it is more important to minimize the worst case waiting time, i.e., the maximum waiting time experienced by a client, independently of his access pattern. This requirement is typically mandated by the service-level agreements (SLAs) that guarantee a certain bound on the time required to obtain information. For example, there might be more requests at the top of the hour, as many clients want to update their internal databases. Alternatively, the distribution of client requests may depend on various global events over which the server has no control. In addition, due to inherent inaccuracy of internal clocks and lack of synchronization, some clients may experience very long waiting times.
Accordingly, what is needed in the art are systems and methods that guarantee low worst-case waiting time, independently of the client behavior. Such methods should not require synchronization between the clients and server and enable to serve diverse clients with different access patterns.